package oj;

import java.util.Scanner;

public class Day32S {
    public static void main(String[] args) {
                long[] arr=new long[100000];
                arr[0]=1;
                arr[1]=2;
                for(int i=2;i<100000;i++){
                    long next=arr[i-1]+arr[i-2];
                    arr[i]=next%1000000;
                }

                Scanner sc=new Scanner(System.in);
                while(sc.hasNext()){
                    int n=sc.nextInt();
                    long f=arr[n-1];
                    if(n<29){
                        System.out.printf("%d\n",f);
                    }else{
                        System.out.printf("%06d\n",f);
                    }
                }
            }
        }
